package com.yubest;

import java.util.*;

/**
 * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 * <p>
 *  
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3,2,3]
 * 输出：[3]
 * 示例 2：
 * <p>
 * 输入：nums = [1]
 * 输出：[1]
 * 示例 3：
 * <p>
 * 输入：[1,1,1,3,3,2,2,2]
 * 输出：[1,2]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 5 * 10^4
 * -10^9 <= nums[i] <= 10^9
 *  
 * <p>
 * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/majority-element-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/22 8:59
 */
public class P0229 {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution229().majorityElement(new int[]{3, 2, 3}).toArray()));

        System.out.println(Arrays.toString(new Solution229().majorityElement(new int[]{1}).toArray()));

        System.out.println(Arrays.toString(new Solution229().majorityElement(new int[]{1, 1, 1, 3, 3, 2, 2, 2}).toArray()));

        System.out.println(Arrays.toString(new Solution229().majorityElement(new int[]{0, 0, 0}).toArray()));

        System.out.println(Arrays.toString(new Solution229().majorityElement(new int[]{2, 1, 1, 3, 1, 4, 5, 6}).toArray()));
    }
}

class Solution229 {

    /**
     * 思路：map存储次数
     * @param nums
     * @return
     */
//    public List<Integer> majorityElement(int[] nums) {
//        Map<Integer, Integer> map = new HashMap<>(nums.length);
//        int n = nums.length / 3;
//        for (int i = 0; i < nums.length; i++) {
//            if (map.containsKey(nums[i])) {
//                map.put(nums[i], map.get(nums[i]) + 1);
//            } else {
//                map.put(nums[i], 1);
//            }
//        }
//        List<Integer> r = new ArrayList<>();
//        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//            if (entry.getValue() > n) {
//                r.add(entry.getKey());
//            }
//        }
//        return r;
//    }

    /**
     * 思路：摩尔投票法
     *
     * @param nums
     * @return
     */
    public List<Integer> majorityElement(int[] nums) {
        //出现大于n/3次的元素只能是2个
        int cand1 = 0, cand2 = 0;
        //用于计算，相同则加一，不同则减一
        int count1 = 0, count2 = 0;
        for (int num : nums) {
            if (count1 > 0 && cand1 == num) {
                count1++;
            } else if (count2 > 0 && cand2 == num) {
                count2++;
            } else if (count1 == 0) {
                cand1 = num;
                count1++;
            } else if (count2 == 0) {
                cand2 = num;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        int c1 = 0, c2 = 0;
        for (int num : nums) {
            //如果计算大于0，说明cand1参与候选
            if (count1 > 0) {
                if (cand1 == num) {
                    c1++;
                }
            }
            //如果计算大于0，说明cand2参与候选
            if (count2 > 0) {
                if (cand2 == num) {
                    c2++;
                }
            }
        }
        List<Integer> r = new ArrayList<>();
        if (c1 > nums.length / 3) {
            r.add(cand1);
        }
        if (c2 > nums.length / 3) {
            r.add(cand2);
        }
        return r;
    }
}
